/*
 * BinaryHeap.h
 *
 *  Created on: Sep 9, 2012
 *      Author: jeffrey
 */

#ifndef BINARYHEAP_H_
#define BINARYHEAP_H_
#include<iostream>
#include<vector>
typedef int T;
using namespace std;
namespace structure {

class BinaryHeap {
public:
	void insert(T val);
	T pop();
	T top() const;
	void buildHeap(T array[], int len);
	BinaryHeap(T array[], int n) {
		buildHeap(array, n);
	}
	~BinaryHeap() {

	}
private:
	inline int parent(int i) {
		return (i - 1) / 2;
	}
	inline int left(int i) {
		return i * 2 + 1;
	}
	inline int right(int i) {
		return i * 2 + 2;
	}
	inline void swap(int i, int j) {
		int tmp=base[j];
		base[j]=base[i];
		base[i]=tmp;
	}
	void down_heapfy(int i) {
		while (true) {
			int l = left(i);
			int r = right(i);
			int curr = i;
			if (l < base.size() && base[curr] > base[l]) {
				curr = l;
			}
			if (r < base.size() && base[curr] > base[r]) {
				curr = r;
			}
			if (curr != i) {
				swap(curr, i);
				i = curr;
			} else
				break;
		}
	}
	void up_heapfy(int i) {
		int p = parent(i);
		while (i > 0 && base[i] < base[p]) {
			swap(i, p);
			i = p;
			p = parent(i);
		}
	}
	vector<T> base;
};

} /* namespace structure */
#endif /* BINARYHEAP_H_ */
